package com.cat.greedyAlgorithm;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/description/
 * @create 2025/10/8 20:39
 * @since JDK17
 */

public class Solution59 {
    public int minTaps(int n, int[] ranges) {
        int[] right = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int start = Math.max(0, i - ranges[i]); //
            right[start] = Math.max(right[start], ranges[i] + i);
        }

        int cur = 0, ans = 0, next = 0;
        for (int i = 0; i < n; i++) {
            next = Math.max(next, right[i]);
            if (i == cur) {
                if (next > cur) {
                    cur = next;
                    ans++;
                } else {
                    return -1;
                }
            }
        }
        return ans;
    }
}
